public class Sort {

    public void insertSort(int[] arr) {
        /**
         * 时间复杂度：O(N^2)
         * 空间复杂度：O(1)
         * 稳定性：稳定
         */
        //i从第二个开始，因为第一个一定是有序的
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            //每一次j在i的后面
            int j = i-1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j+1] = arr[j];
                } else {
                    arr[j+1] = tmp;
                    break;
                }
            }
            //第一次当j<0时
            arr[j+1] = tmp;
        }
    }

    public void shellSort(int[] arr) {
        /**
         * 时间复杂度：n^1.3 ~ n^1.5
         * 空间复杂度：O(1)
         * 不稳定
         */
        int gap = arr.length;
        while (gap > 1) {
            //缩小增量
            gap /= 2;
            shell(arr, gap);
        }
    }
    private void shell(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for (; j >= 0 ; j -= gap) {
                if (arr[j] > tmp) {
                    arr[j+gap] = arr[j];
                } else {
                    arr[j+gap] = tmp;
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }

    public void selectSort(int[] arr) {
        /**
         * 时间复杂度：O(N^2)
         * 空间复杂度：O(1)
         * 稳定性：不稳定排序
         */
        for (int i = 0; i < arr.length; i++) {
            //minIndex用于标记最小数的下标
            int minIndex = i;
            //每趟找到一个最小的
            for (int j = i+1; j < arr.length; j++) {
                //每次和最小数比较大小
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            //每次将最小数和arr[i]进行交换，可以将最小的排到前面
            swap(arr, i, minIndex);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //selectSort的优化，但时间复杂度依旧是O(N^2)
    public void selectSort2(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right; i++) {
                if (arr[minIndex] > arr[i]) {
                    minIndex = i;
                }
                if (arr[maxIndex] < arr[i]) {
                    maxIndex = i;
                }
            }
            swap(arr, left, minIndex);
            //最大值的下标是left时，防止最大值被换走了
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(arr, right, maxIndex);
            left++;
            right--;
        }
    }

    public void heapSort(int[] arr) {
        /**
         * 时间复杂度：O(n*logN)
         * 空间复杂度：O(1)
         * 稳定性：不稳定
         */
        createHeap(arr);
        int end = arr.length - 1;
        while (end > 0) {
            swap(arr, 0, end);
            siftDown(arr, end, 0);
            end--;
        }
    }

    private void createHeap(int[] arr) {
        for (int parent = (arr.length-1-1)/2; parent >= 0 ; parent--) {
            siftDown(arr, arr.length, parent);
        }
    }

    /**
     *
     * @param arr
     * @param length 每颗子树结束的节点
     * @param parent 每颗子树调整的跟节点
     */
    private void siftDown(int[] arr, int length, int parent) {
        int child = 2 * parent + 1;
        while (child < length) {
            if (child+1 < length && arr[child] < arr[child+1]) {
                child++;
            }
            if (arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    /**
     * 时间复杂度：O(N^2)【没有优化的情况下,优化的情况下最好可以达到O(N)】
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param arr
     */
    public void bubbleSort(int[] arr) {
        //趟数（10个元素只需要9躺）
        for (int i = 0; i < arr.length-1; i++) {
            boolean flag = false;
            //每趟交换的次数
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j] > arr[j+1]) {
                    swap(arr,j,j+1);
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
    }

    public void quickSort(int[] arr) {
        quick(arr, 0, arr.length-1);
    }

    private void quick(int[] arr, int left, int right) {
        //递归结束条件
        if (left >= right) {
            return;
        }
        //找到基准值
        int pivot = Partition(arr, left, right);
        //递归基准值的左边
        quick(arr, left, pivot-1);
        //递归基准值的右边
        quick(arr, pivot+1, right);
    }

    private int Partition(int[] arr, int start, int end) {
        //定义起始位置的为基准值
        int tmp = arr[start];
        //基准值位置的下标
        int tmpStart = start;
        while (start < end) {
            //从后往前找到比基准值小的元素
            while (start < end && arr[end] >= tmp) {
                end--;
            }
            //从前往后找到比基准值大的元素
            while (start < end && arr[start] <= tmp) {
                start++;
            }
            //交换找到的这两个元素的位置
            swap(arr, start, end);
        }
        //start和end相遇时将此时的元素和基准值元素交换
        swap(arr, start, tmpStart);
        return start;
    }


}
